﻿using System;
using System.Collections.Generic;
using System.IO;

namespace Sims3Package
{
    /// <summary>
    /// Used by Sims3Package library
    /// </summary>
    internal static class Compression
    {
        internal static Stream Compress(Stream tocompress)
        {
            byte[] data = new byte[(int)tocompress.Length];
            tocompress.Read(data, 0, data.Length);
            return Compress(data);
        }

        internal static byte[] CompressToByte(byte[] tocompress)
        {
            byte[] res;
            bool smaller = Tiger.DBPFCompression.Compress(tocompress, out res);
            return smaller ? res : tocompress;
        }

        internal static byte[] CompressToByte(Stream tocompress)
        {
            byte[] data = new byte[(int)tocompress.Length];
            tocompress.Read(data, 0, data.Length);
            return CompressToByte(data);
        }
        
        internal static Stream Compress(byte[] tocompress)
        {
            byte[] res;
            bool smaller = Tiger.DBPFCompression.Compress(tocompress, out res);
            return new MemoryStream(smaller ? res : tocompress);
        }

        /// <summary>
        /// De-compress the stream
        /// </summary>
        /// <param name="compressed">Stream to decompressed</param>
        /// <returns>Uncompressed stream</returns>
        internal static Stream Decompress(Stream compressed)
        {
            if (compressed == null) return null;

            compressed.Position = 0;
            BinaryReader r = new BinaryReader(compressed);

            bool type = r.ReadByte() != 0x80;
            if (r.ReadByte() != 0xFB)
                return null;
            byte[] sizeArray = new byte[4];


            for (int i = type ? 2 : 3; i >= 0; i--)
                sizeArray[i] = r.ReadByte();

            byte[] Data = new byte[BitConverter.ToInt32(sizeArray, 0)];

            int position = 0;
            while (position < Data.Length)
            {
                byte byte0 = r.ReadByte();
                if (byte0 <= 0x7F)
                {
                    // Read info
                    byte byte1 = r.ReadByte();
                    int numPlainText = byte0 & 0x03;
                    int numToCopy = ( (byte0 & 0x1C) >> 2) + 3;
                    int copyOffest = ((byte0 & 0x60) << 3) + byte1 + 1;

                    CopyPlainText(ref r, ref Data, numPlainText, ref position);

                    CopyCompressedText(ref r, ref Data, numToCopy, ref position, copyOffest);

                }
                else if (byte0 <= 0XBF && byte0 > 0x7F)
                {
                    // Read info
                    byte byte1 = r.ReadByte();
                    byte byte2 = r.ReadByte();
                    int numPlainText = ((byte1 & 0xC0) >> 6) & 0x03;
                    int numToCopy = (byte0 & 0x3F) + 4;
                    int copyOffest = ((byte1 & 0x3F) << 8) + byte2 + 1;

                    CopyPlainText(ref r, ref Data, numPlainText, ref position);

                    CopyCompressedText(ref r, ref Data, numToCopy, ref position, copyOffest);
                }
                else if (byte0 <= 0xDF && byte0 > 0xBF)
                {
                    // Read info
                    byte byte1 = r.ReadByte();
                    byte byte2 = r.ReadByte();
                    byte byte3 = r.ReadByte();
                    int numPlainText = byte0 & 0x03;
                    int numToCopy = ((byte0 & 0x0C) << 6) + byte3 + 5;
                    int copyOffest = ((byte0 & 0x10) << 12) + (byte1 << 8) + byte2 + 1;

                    CopyPlainText(ref r, ref Data, numPlainText, ref position);

                    CopyCompressedText(ref r, ref Data, numToCopy, ref position, copyOffest);
                }
                else if (byte0 <= 0xFB && byte0 > 0xDF)
                {
                    // Read info
                    int numPlainText = ((byte0 & 0x1F) << 2) + 4;

                    CopyPlainText(ref r, ref Data, numPlainText, ref position);
                    
                }
                else if (byte0 <= 0xFF && byte0 > 0xFB)
                {
                    // Read info
                    int numPlainText = (byte0 & 0x03);

                    CopyPlainText(ref r, ref Data, numPlainText, ref position);
                }
            }

            return new MemoryStream(Data);
        }

        internal static bool IsCompressed(byte[] Data)
        {
            if (Data.Length < 3) return false;
            if (Data[1] == 0xFB && Data[Data.Length - 1] >= 0xFC && Data[Data.Length - 1] <= 0xFF && (Data[0] == 0x10 || Data[0] == 0x40 || Data[0] == 0x80)) return true;
            return false;
        }

        internal static bool IsCompressed(Stream s)
        {
            BinaryReader r = new BinaryReader(s);
            byte type = r.ReadByte();
            byte sig = r.ReadByte();
            if ((type == 0x10 || type == 0x40 || type == 0x80) && sig == 0xFB)
                return true;
            return false;
        }

        static void CopyPlainText(ref BinaryReader r, ref byte[] Data, int numPlainText, ref int position)
        {
            // Copy data one at a time
            for (int i = 0; i < numPlainText; position++, i++)
            {
                Data[position] = r.ReadByte();
            }
        }

        static void CopyCompressedText(ref BinaryReader r, ref byte[] Data, int numToCopy, ref int position, int copyOffest)
        {
            int currentPosition = position;
            // Copy data one at a time
            for (int i = 0; i < numToCopy; i++, position++)
            {
                Data[position] = Data[currentPosition - copyOffest + i];
            }
        }

        internal static Stream Decompress(byte[] compressed)
        {
            using(MemoryStream s = new MemoryStream(compressed))
            {
                return Decompress(s);
            }
            
        }


        /// <summary>
        /// Returns the length of un-compressed resource stream
        /// </summary>
        /// <param name="compressed">Compressed resource stream</param>
        /// <returns></returns>
        internal static UInt32 GetMemsize(Stream compressed)
        {
            BinaryReader r = new BinaryReader(compressed);
            bool type = r.ReadByte() != 0x80;
            if (r.ReadByte() != 0xFB)
                return UInt32.MaxValue;
            byte[] size = new byte[4];

            if (type)
            {
                for (int i = 2; i >= 0; i--)
                    size[i] = r.ReadByte();
            }
            else
            {
                for (int i = 3; i >= 0; i--)
                    size[i] = r.ReadByte();
            }

            return BitConverter.ToUInt32(size, 0);
        }
        /// <summary>
        /// Returns the length of compressed resource stream
        /// </summary>
        /// <param name="resourcestream">Un-compressed resource stream</param>
        /// <returns></returns>
        internal static Int32 GetFilesize(Stream resourcestream)
        {
            if (resourcestream == null) return 0;
            if (resourcestream.Length == 0) return 0;
            resourcestream.Position = 0;
            return (Int32)(Compress(resourcestream).Length);
        }

        internal static Int32 GetFilesize(byte[] data)
        {
            return (Int32)CompressToByte(data).Length;
        }

        
        
    }
}

/*
 * The following code was provided by Tiger
**/

namespace Tiger
{
    class DBPFCompression
    {
        public DBPFCompression(int level)
        {
            mTracker = CreateTracker(level, out mBruteForceLength);
        }

        public DBPFCompression(int blockinterval, int lookupstart, int windowlength, int bucketdepth, int bruteforcelength)
        {
            mTracker = CreateTracker(blockinterval, lookupstart, windowlength, bucketdepth);
            mBruteForceLength = bruteforcelength;
        }

        private int mBruteForceLength;
        private IMatchtracker mTracker;

        private byte[] mData;

        private int mSequenceSource;
        private int mSequenceLength;
        private int mSequenceDest;
        private bool mSequenceFound;

        public static bool Compress(byte[] data, out byte[] compressed)
        {
            DBPFCompression compressor = new DBPFCompression(5);
            compressed = compressor.Compress(data);
            return (compressed != null);
        }

        public static bool Compress(byte[] data, out byte[] compressed, int level)
        {
            DBPFCompression compressor = new DBPFCompression(level);
            compressed = compressor.Compress(data);
            return (compressed != null);
        }

        public byte[] Compress(byte[] data)
        {
            bool endisvalid = false;
            List<byte[]> compressedchunks = new List<byte[]>();
            int compressedidx = 0;
            int compressedlen = 0;

            if (data.Length < 16 || data.LongLength > UInt32.MaxValue)
                return null;

            mData = data;

            try
            {
                int lastbytestored = 0;

                while (compressedidx < data.Length)
                {
                    if (data.Length - compressedidx < 4)
                    {
                        // Just copy the rest
                        byte[] chunk = new byte[data.Length - compressedidx + 1];
                        chunk[0] = (byte)(0xFC | (data.Length - compressedidx));
                        Array.Copy(data, compressedidx, chunk, 1, data.Length - compressedidx);
                        compressedchunks.Add(chunk);
                        compressedidx += chunk.Length - 1;
                        compressedlen += chunk.Length;

                        endisvalid = true;
                        continue;
                    }

                    while (compressedidx > lastbytestored - 3)
                        mTracker.Addvalue(data[lastbytestored++]);

                    // Search ahead in blocks of 4 bytes for a match until one is found
                    // Record the best match if multiple are found
                    mSequenceSource = 0;
                    mSequenceLength = 0;
                    mSequenceDest = int.MaxValue;
                    mSequenceFound = false;
                    do
                    {
                        for (int loop = 0; loop < 4; loop++)
                        {
                            if (lastbytestored < data.Length)
                                mTracker.Addvalue(data[lastbytestored++]);
                            FindSequence(lastbytestored - 4);
                        }
                    }
                    while (!mSequenceFound && lastbytestored + 4 <= data.Length);

                    if (!mSequenceFound)
                        mSequenceDest = mData.Length;

                    // If the next match is more than four bytes away, put in codes to read uncompressed data
                    while (mSequenceDest - compressedidx >= 4)
                    {
                        int tocopy = (mSequenceDest - compressedidx) & ~3;
                        if (tocopy > 112)
                            tocopy = 112;

                        byte[] chunk = new byte[tocopy + 1];
                        chunk[0] = (byte)(0xE0 | ((tocopy >> 2) - 1));
                        Array.Copy(data, compressedidx, chunk, 1, tocopy);
                        compressedchunks.Add(chunk);
                        compressedidx += tocopy;
                        compressedlen += chunk.Length;
                    }

                    if (mSequenceFound)
                    {
                        byte[] chunk = null;
                        /*
                         * 00-7F  0oocccpp oooooooo
                         *   Read 0-3
                         *   Copy 3-10
                         *   Offset 0-1023
                         *   
                         * 80-BF  10cccccc ppoooooo oooooooo
                         *   Read 0-3
                         *   Copy 4-67
                         *   Offset 0-16383
                         *   
                         * C0-DF  110cccpp oooooooo oooooooo cccccccc
                         *   Read 0-3
                         *   Copy 5-1028
                         *   Offset 0-131071
                         *   
                         * E0-FC  111ppppp
                         *   Read 4-128 (Multiples of 4)
                         *   
                         * FD-FF  111111pp
                         *   Read 0-3
                         */
                        //if (FindRunLength(data, seqstart, compressedidx + seqidx) < seqlength)
                        //{
                        //    break;
                        //}
                        while (mSequenceLength > 0)
                        {
                            int thislength = mSequenceLength;
                            if (thislength > 1028)
                                thislength = 1028;
                            mSequenceLength -= thislength;

                            int offset = mSequenceDest - mSequenceSource - 1;
                            int readbytes = mSequenceDest - compressedidx;

                            mSequenceSource += thislength;
                            mSequenceDest += thislength;

                            if (thislength > 67 || offset > 16383)
                            {
                                chunk = new byte[readbytes + 4];
                                chunk[0] = (byte)(0xC0 | readbytes | (((thislength - 5) >> 6) & 0x0C) | ((offset >> 12) & 0x10));
                                chunk[1] = (byte)((offset >> 8) & 0xFF);
                                chunk[2] = (byte)(offset & 0xFF);
                                chunk[3] = (byte)((thislength - 5) & 0xFF);
                            }
                            else if (thislength > 10 || offset > 1023)
                            {
                                chunk = new byte[readbytes + 3];
                                chunk[0] = (byte)(0x80 | ((thislength - 4) & 0x3F));
                                chunk[1] = (byte)(((readbytes << 6) & 0xC0) | ((offset >> 8) & 0x3F));
                                chunk[2] = (byte)(offset & 0xFF);
                            }
                            else
                            {
                                chunk = new byte[readbytes + 2];
                                chunk[0] = (byte)((readbytes & 0x3) | (((thislength - 3) << 2) & 0x1C) | ((offset >> 3) & 0x60));
                                chunk[1] = (byte)(offset & 0xFF);
                            }

                            if (readbytes > 0)
                                Array.Copy(data, compressedidx, chunk, chunk.Length - readbytes, readbytes);

                            compressedchunks.Add(chunk);
                            compressedidx += thislength + readbytes;
                            compressedlen += chunk.Length;
                        }
                    }
                }

                if (compressedlen + 6 < data.Length)
                {
                    int chunkpos;
                    byte[] compressed;

                    if (data.Length > 0xFFFFFF)
                    {
                        // Activate the large data bit for > 16mb uncompressed data
                        compressed = new byte[compressedlen + 6 + (endisvalid ? 0 : 1)];
                        compressed[0] = 0x10 | 0x80; // 0x80 = length is 4 bytes
                        compressed[1] = 0xFB;
                        compressed[2] = (byte)(data.Length >> 24);
                        compressed[3] = (byte)(data.Length >> 16);
                        compressed[4] = (byte)(data.Length >> 8);
                        compressed[5] = (byte)(data.Length);
                        chunkpos = 6;
                    }
                    else
                    {
                        compressed = new byte[compressedlen + 5 + (endisvalid ? 0 : 1)];
                        compressed[0] = 0x10;
                        compressed[1] = 0xFB;
                        compressed[2] = (byte)(data.Length >> 16);
                        compressed[3] = (byte)(data.Length >> 8);
                        compressed[4] = (byte)(data.Length);
                        chunkpos = 5;
                    }

                    for (int loop = 0; loop < compressedchunks.Count; loop++)
                    {
                        Array.Copy(compressedchunks[loop], 0, compressed, chunkpos, compressedchunks[loop].Length);
                        chunkpos += compressedchunks[loop].Length;
                    }
                    if (!endisvalid)
                        compressed[compressed.Length - 1] = 0xfc;
                    return compressed;
                }

                return null;
            }
            finally
            {
                mData = null;
                mTracker.Reset();
            }
        }

        private void FindSequence(int startindex)
        {
            // Try a straight forward brute force first
            int end = -mBruteForceLength;
            if (startindex < mBruteForceLength)
                end = -startindex;

            byte searchforbyte = mData[startindex];

            for (int loop = -1; loop >= end && mSequenceLength < 1028; loop--)
            {
                byte curbyte = mData[loop + startindex];
                if (curbyte != searchforbyte)
                    continue;

                int len = FindRunLength(startindex + loop, startindex);

                if (len <= mSequenceLength
                    || len < 3
                    || len < 4 && loop <= -1024
                    || len < 5 && loop <= -16384)
                    continue;

                mSequenceFound = true;
                mSequenceSource = startindex + loop;
                mSequenceLength = len;
                mSequenceDest = startindex;
            }

            // Use the look-up table next
            int matchloc;
            if (mSequenceLength < 1028 && mTracker.FindMatch(out matchloc))
            {
                do
                {
                    int len = FindRunLength(matchloc, startindex);
                    if (len < 5)
                        continue;

                    mSequenceFound = true;
                    mSequenceSource = matchloc;
                    mSequenceLength = len;
                    mSequenceDest = startindex;
                }
                while (mSequenceLength < 1028 && mTracker.Nextmatch(out matchloc));
            }
        }

        private int FindRunLength(int src, int dst)
        {
            int endsrc = src + 1;
            int enddst = dst + 1;
            while (enddst < mData.Length && mData[endsrc] == mData[enddst] && enddst - dst < 1028)
            {
                endsrc++;
                enddst++;
            }

            return enddst - dst;
        }

        private interface IMatchtracker
        {
            bool FindMatch(out int where);
            bool Nextmatch(out int where);
            void Addvalue(byte val);
            void Reset();
        }

        static IMatchtracker CreateTracker(int blockinterval, int lookupstart, int windowlength, int bucketdepth)
        {
            if (bucketdepth <= 1)
                return new SingledepthMatchTracker(blockinterval, lookupstart, windowlength);
            else
                return new DeepMatchTracker(blockinterval, lookupstart, windowlength, bucketdepth);
        }

        static IMatchtracker CreateTracker(int level, out int bruteforcelength)
        {
            switch (level)
            {
                case 0:
                    bruteforcelength = 0;
                    return CreateTracker(4, 0, 16384, 1);
                case 1:
                    bruteforcelength = 0;
                    return CreateTracker(2, 0, 32768, 1);
                case 2:
                    bruteforcelength = 0;
                    return CreateTracker(1, 0, 65536, 1);
                case 3:
                    bruteforcelength = 0;
                    return CreateTracker(1, 0, 131000, 2);
                case 4:
                    bruteforcelength = 16;
                    return CreateTracker(1, 16, 131000, 2);
                case 5:
                    bruteforcelength = 16;
                    return CreateTracker(1, 16, 131000, 5);
                case 6:
                    bruteforcelength = 32;
                    return CreateTracker(1, 32, 131000, 5);
                case 7:
                    bruteforcelength = 32;
                    return CreateTracker(1, 32, 131000, 10);
                case 8:
                    bruteforcelength = 64;
                    return CreateTracker(1, 64, 131000, 10);
                case 9:
                    bruteforcelength = 128;
                    return CreateTracker(1, 128, 131000, 20);
                default:
                    return CreateTracker(5, out bruteforcelength);
            }
        }

        private class SingledepthMatchTracker : IMatchtracker
        {
            public SingledepthMatchTracker(int blockinterval, int lookupstart, int windowlength)
            {
                mInterval = blockinterval;
                if (lookupstart > 0)
                {
                    mPendingValues = new UInt32[lookupstart / blockinterval];
                    mQueueLength = mPendingValues.Length * blockinterval;
                }
                else
                    mQueueLength = 0;
                mInsertedValues = new UInt32[windowlength / blockinterval - lookupstart / blockinterval];
                mWindowStart = -(mInsertedValues.Length + lookupstart / blockinterval) * blockinterval - 4;
            }

            public void Reset()
            {
                mLookupTable.Clear();
                mRunningValue = 0;

                mRollingInterval = 0;
                mWindowStart = -(mInsertedValues.Length + (mPendingValues != null ? mPendingValues.Length : 0)) * mInterval - 4;
                mDataLength = 0;

                mInitialized = false;
                mInsertLocation = 0;
                mPendingOffset = 0;

                // No need to clear the arrays, the values will be ignored by the next time around
            }

            // Current 32 bit value of the last 4 bytes
            private UInt32 mRunningValue;

            // How often to insert into the table
            private int mInterval;
            // Avoid division by using a rolling count instead
            private int mRollingInterval;

            // How many bytes to queue up before adding it to the lookup table
            private int mQueueLength;

            // Queued up values for future matches
            private UInt32[] mPendingValues;
            private int mPendingOffset;

            // Bytes processed so far
            private int mDataLength;
            private int mWindowStart;

            // Four or more bytes read
            private bool mInitialized;

            // Values values pending removal
            private UInt32[] mInsertedValues;
            private int mInsertLocation;

            // Hash of seen values
            private Dictionary<UInt32, int> mLookupTable = new Dictionary<uint, int>();

            #region IMatchtracker Members

            // Never more than one match with a depth of 1
            public bool Nextmatch(out int where)
            {
                where = 0;
                return false;
            }

            public void Addvalue(byte val)
            {
                if (mInitialized)
                {
                    mRollingInterval++;
                    // Time to add a value to the table
                    if (mRollingInterval == mInterval)
                    {
                        mRollingInterval = 0;
                        // Remove a value from the table if the window just rolled past it
                        if (mWindowStart >= 0)
                        {
                            int idx;
                            if (mInsertLocation == mInsertedValues.Length)
                                mInsertLocation = 0;
                            UInt32 oldval = mInsertedValues[mInsertLocation];
                            if (mLookupTable.TryGetValue(oldval, out idx) && idx == mWindowStart)
                                mLookupTable.Remove(oldval);
                        }
                        if (mPendingValues != null)
                        {
                            // Pop the top of the queue and put it in the table
                            if (mDataLength > mQueueLength + 4)
                            {
                                UInt32 poppedval = mPendingValues[mPendingOffset];
                                mInsertedValues[mInsertLocation] = poppedval;
                                mInsertLocation++;
                                if (mInsertLocation > mInsertedValues.Length)
                                    mInsertLocation = 0;

                                // Put it into the table
                                mLookupTable[poppedval] = mDataLength - mQueueLength - 4;
                            }
                            // Push the next value onto the queue
                            mPendingValues[mPendingOffset] = mRunningValue;
                            mPendingOffset++;
                            if (mPendingOffset == mPendingValues.Length)
                                mPendingOffset = 0;
                        }
                        else
                        {
                            // No queue, straight to the dictionary
                            mInsertedValues[mInsertLocation] = mRunningValue;
                            mInsertLocation++;
                            if (mInsertLocation > mInsertedValues.Length)
                                mInsertLocation = 0;

                            mLookupTable[mRunningValue] = mDataLength - 4;
                        }
                    }
                }
                else
                {
                    mRollingInterval++;
                    if (mRollingInterval == mInterval)
                        mRollingInterval = 0;
                    mInitialized = (mDataLength == 3);
                }

                mRunningValue = (mRunningValue << 8) | val;
                mDataLength++;
                mWindowStart++;
            }

            public bool FindMatch(out int where)
            {
                return mLookupTable.TryGetValue(mRunningValue, out where);
            }

            #endregion
        }

        private class DeepMatchTracker : IMatchtracker
        {
            public DeepMatchTracker(int blockinterval, int lookupstart, int windowlength, int bucketdepth)
            {
                mInterval = blockinterval;
                if (lookupstart > 0)
                {
                    mPendingValues = new UInt32[lookupstart / blockinterval];
                    mQueueLength = mPendingValues.Length * blockinterval;
                }
                else
                    mQueueLength = 0;
                mInsertedValues = new UInt32[windowlength / blockinterval - lookupstart / blockinterval];
                mWindowStart = -(mInsertedValues.Length + lookupstart / blockinterval) * blockinterval - 4;
                mBucketDepth = bucketdepth;
            }

            public void Reset()
            {
                mLookupTable.Clear();
                mRunningValue = 0;

                mRollingInterval = 0;
                mWindowStart = -(mInsertedValues.Length + (mPendingValues != null ? mPendingValues.Length : 0)) * mInterval - 4;
                mDataLength = 0;

                mInitialized = false;
                mInsertLocation = 0;
                mPendingOffset = 0;

                mCurrentMatch = null;

                // No need to clear the arrays, the values will be ignored by the next time around
            }

            private int mBucketDepth;

            // Current 32 bit value of the last 4 bytes
            private UInt32 mRunningValue;

            // How often to insert into the table
            private int mInterval;
            // Avoid division by using a rolling count instead
            private int mRollingInterval;

            // How many bytes to queue up before adding it to the lookup table
            private int mQueueLength;

            // Queued up values for future matches
            private UInt32[] mPendingValues;
            private int mPendingOffset;

            // Bytes processed so far
            private int mDataLength;
            private int mWindowStart;

            // Four or more bytes read
            private bool mInitialized;

            // Values values pending removal
            private UInt32[] mInsertedValues;
            private int mInsertLocation;

            // Hash of seen values
            private Dictionary<UInt32, List<int>> mLookupTable = new Dictionary<uint, List<int>>();

            // Save allocating items unnecessarily
            private Stack<List<int>> mUnusedLists = new Stack<List<int>>();

            private List<int> mCurrentMatch;
            private int mCurrentMatchIndex;

            #region IMatchtracker Members

            public void Addvalue(byte val)
            {
                if (mInitialized)
                {
                    mRollingInterval++;
                    // Time to add a value to the table
                    if (mRollingInterval == mInterval)
                    {
                        mRollingInterval = 0;
                        // Remove a value from the table if the window just rolled past it
                        if (mWindowStart > 0)
                        {
                            List<int> locations;
                            if (mInsertLocation == mInsertedValues.Length)
                                mInsertLocation = 0;
                            UInt32 oldval = mInsertedValues[mInsertLocation];
                            if (mLookupTable.TryGetValue(oldval, out locations) && locations[0] == mWindowStart)
                            {
                                locations.RemoveAt(0);
                                if (locations.Count == 0)
                                {
                                    mLookupTable.Remove(oldval);
                                    mUnusedLists.Push(locations);
                                }
                            }
                        }
                        if (mPendingValues != null)
                        {
                            // Pop the top of the queue and put it in the table
                            if (mDataLength > mQueueLength + 4)
                            {
                                UInt32 poppedval = mPendingValues[mPendingOffset];
                                mInsertedValues[mInsertLocation] = poppedval;
                                mInsertLocation++;
                                if (mInsertLocation > mInsertedValues.Length)
                                    mInsertLocation = 0;

                                // Put it into the table
                                List<int> locations;
                                if (mLookupTable.TryGetValue(poppedval, out locations))
                                {
                                    // Check if the bucket runneth over
                                    if (locations.Count == mBucketDepth)
                                        locations.RemoveAt(0);
                                }
                                else
                                {
                                    // Allocate a new bucket
                                    if (mUnusedLists.Count > 0)
                                        locations = mUnusedLists.Pop();
                                    else
                                        locations = new List<int>();
                                    mLookupTable[poppedval] = locations;
                                }
                                locations.Add(mDataLength - mQueueLength - 4);
                            }
                            // Push the next value onto the queue
                            mPendingValues[mPendingOffset] = mRunningValue;
                            mPendingOffset++;
                            if (mPendingOffset == mPendingValues.Length)
                                mPendingOffset = 0;
                        }
                        else
                        {
                            mInsertedValues[mInsertLocation] = mRunningValue;
                            mInsertLocation++;
                            if (mInsertLocation > mInsertedValues.Length)
                                mInsertLocation = 0;

                            // Put it into the table
                            List<int> locations;
                            if (mLookupTable.TryGetValue(mRunningValue, out locations))
                            {
                                // Check if the bucket runneth over
                                if (locations.Count == mBucketDepth)
                                    locations.RemoveAt(0);
                            }
                            else
                            {
                                // Allocate a new bucket
                                if (mUnusedLists.Count > 0)
                                    locations = mUnusedLists.Pop();
                                else
                                    locations = new List<int>();
                                mLookupTable[mRunningValue] = locations;
                            }
                            locations.Add(mDataLength - 4);
                        }
                    }
                }
                else
                {
                    mRollingInterval++;
                    if (mRollingInterval == mInterval)
                        mRollingInterval = 0;
                    mInitialized = (mDataLength == 3);
                }
                mRunningValue = (mRunningValue << 8) | val;
                mDataLength++;
                mWindowStart++;
            }

            public bool Nextmatch(out int where)
            {
                if (mCurrentMatch != null && mCurrentMatchIndex < mCurrentMatch.Count)
                {
                    where = mCurrentMatch[mCurrentMatchIndex];
                    mCurrentMatchIndex++;
                    return true;
                }
                where = -1;
                return false;
            }

            public bool FindMatch(out int where)
            {
                if (mLookupTable.TryGetValue(mRunningValue, out mCurrentMatch))
                {
                    mCurrentMatchIndex = 1;
                    where = mCurrentMatch[0];
                    return true;
                }
                mCurrentMatch = null;
                where = -1;
                return false;
            }

            #endregion
        }
    }
}